Before proceeding with a discussion of the background of the invention, it should be noted that clipping often occurs in a coordinate space other than the device coordinate space, such as world coordinate space, and the rectangular region against which the lines are clipped is normally referred to as a window. On the other hand, since the viewport refers to a specific region of the device display area it is defined in terms of device coordinates. Thus window-to-viewport mapping is required before vector-to-raster conversion is performed, as is well known. Nevertheless, it is quite possible to perform clipping in the device coordinate space and in such case the window and the viewport are one and the same. For convenience, therefore, in the present specification we use the single term viewport to include both the viewport proper, i.e. the rectangular region of the display area defined in device coordinates in which the clipped lines are to be viewed, and also the window against which the lines are clipped by the clipping mechanism, which may or may not be in device coordinates. It is therefore to be understood that when the term viewport is used in relation to clipping it may refer to a window (the predecessor of the viewport proper) in a coordinate space other than device coordinate space, with window-to-viewport mapping being implied if not explicitly stated. Furthermore, where the specification refers to the clipping of a line by the clipping mechanism, it is to be understood that the line is in the coordinate system in which the clipping mechanism operates.
Conventional line clipping mechanisms use the Cohen-Sutherland (CS) technique which is described, for example, on pages 146 and 147 of the book "Fundamentals of Interactive Computer Graphics" by Foley and Van Damm, published 1982 by Addison-Wesley Publishing Co. Ltd. In this technique the area surrounding the viewport is divided into eight regions, herein referred to as outregions, and different outcodes are assigned to the various regions and to the viewport. Certain lines can be quickly eliminated from consideration for clipping by inspection of the outcodes of their endpoints, either because they lie entirely to one side of the viewport or because they lie entirely within the viewport. In the former case the lines are said to be trivially rejected, in the latter case trivially accepted.
The remaining lines may or may not intersect the viewport, and therefore in general the intersection of each line with each of the four boundaries of the viewport is calculated in turn in order to determine the points of intersection, if any, of the line with the edges of the viewport. While in many cases the edge intersections will be found before all four calculations have been made, some lines will nevertheless require the full four calculations. In this connection it is to be understood that in the present specification the term boundary refers to one of the four imaginary infinite lines in the coordinate space concerned, two vertical and two horizontal, which enclose and thereby define the viewport, whereas the term edge refers to only that part of each boundary which lies between the two parallel boundaries perpendicular to it. Furthermore, we are not concerned in the present specification with strictly vertical, horizontal and .+-.45.degree. lines which do not require complex intersection calculations to be made.
Having determined the intersection points of the line with the viewport, the parts outside the viewport are discarded and information defining the X,Y coordinates of the endpoints of the remaining clipped lines is passed to the VTR, if necessary after mapping as referred to above. This line information, which may be passed directly to the VTR or, for example, indirectly via a display file which is accessed by the VTR, may define both endpoint coordinates explicitly or, where the line starts at the end of a previous line, one endpoint may be defined implicitly by providing only the coordinates of the endpoint remote from the junction with the previous line. The VTR takes the line information thus provided and, using the incremental line drawing mechanism, plots the line pel by pel into the refresh buffer.
As will be recognized by those familiar with point plotting techniques, an incremental line drawing mechanism is a mechanism of the kind in which successive incrementally displaced pairs of X,Y display coordinates are generated by performing one iteration of an interactive computation in respect of each consecutive coordinate unit along a given axis of the line, starting a one endpoint of the line and proceeding towards the other. The mechanism is regarded as stepping along the given axis of the line, and the stepping axis may be the major axis of the line, i.e. that X or Y axis relative to which the line is inclined at less than .+-.45.degree., or the minor axis of the line, i.e. the axis normal to the major axis, depending on the nature of the mechanism. Thus, for example, DDA and Bresenham line drawing mechanisms step along the major axis of the line and for each major axis coordinate generate one minor axis coordinate. On the other hand, run-length line drawing mechanism step along the minor axis of the line and for each minor axis coordinate generate a plurality (run) of major axis coordinates. Clearly, one coordinate of each pair generated by the mechanism is simply the current coordinate along the relevant stepping axis. As is well known, the number of iterations performed by the mechanism is controlled by a stepping loop count which is conventionally set by the VTR to the magnitude of the coordinate difference along the stepping axis between the endpoints of the line as defined by the line information supplied by the clipping mechanism.
Conventional incremental line drawing mechanisms generally require each end of the line to lie within the viewport or to be clipped to an edge of the viewport by the clipping mechanism. However, the calculation of the intersection of a line with a viewport boundary is very time-consuming, and this is a particular disadvantage in the case of interactive graphics where a large number of lines must often be processed as quickly as possible to provide a fast feedback to the operator. Thus any improvement in the efficiency of clipping and line drawing operations, in particular by reducing the average number of intersection calculations required per line, will have a significant impact on the time required to process lines for display.
It is therefore an object of the invention to provide an improved line clipping or drawing mechanism which reduces the average number of intersection calculations per line.